#include"heap.h"

void HeapCreate(HP* hp,HPDataType *a,int n)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (hp->a==NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	memcpy(hp->a, a, sizeof(HPDataType) * n);
	//void *memcpy(void *str1, const void *str2, size_t n) 
	//从存储区 str2 复制 n 个字节到存储区 str1。
	hp->size = hp->capacity = n;
	for (int i=(n-1-1)/2;i>0;i--)
	{
		AdjustDown(hp->a, n, i);
	}
}

void Swap(HPDataType* px,HPDataType* py)
{
	HPDataType* tmp = *px;
	*px = *py;
	*py = tmp;
}

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}


void HeapDestory(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

//向上调整
//size为数组大小，child为新插入的数据位置
void AdjustUp(int *a,int size,int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		//大堆
		//if (a[child] > a[parent])
		//小堆
		if(a[child]<a[parent])
		{
			//父子数值交换
			Swap(&a[child], &a[parent]);

			//更新父子结点
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆插入数据堆其他结点没有影响
//可能会影响它到根节点的路径上的结点关系
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size==hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (tmp==NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size, hp->size - 1);
}


void AdjustDown(int *a,int size,int parent)
{
	assert(a);
	int child = parent * 2 + 1;//左孩子
	while (child<size)
	{
		//选更大的孩子结点，child+1为右孩子
		//if (child+1<size&&a[child+1]>a[child])
		//选更小的孩子节点
		if(child+1<size&&a[child+1]<a[child])
		{
			child++;//如果右孩子值更大/小，那么child指向右孩子
		}
		//大堆：如果大的孩子大于父亲则交换
		//if (a[child]>a[parent])
		//小堆，如果小的孩子小于父亲则交换
		if(a[child]<a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//再进行向下调整算法
void HeapPop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);
	Swap(&hp->a[0], &hp->a[hp->size - 1]);//将堆顶数据与数组中最后一个数据交换
	hp->size--;//删除数组中的最后一个数据
	AdjustDown(hp->a, hp->size,0);//传入数组，数组的大小，向下调整起始位置
}

void HeapPrintf(HP* hp)
{
	assert(hp);
	for(int i=0;i<hp->size;i++)
	{
		printf("%d ",hp->a[i]);
	}
	printf("\n");
}

HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);
	return hp->a[0];
}

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

//堆排序
void HeapSort(int*a ,int n)
{
//升序调整堆--O(N*logN)
	for (int i = 0;i<n;i++)
	{
		AdjustUp(a, n, i);
	}
//降序调整堆--O(N)
//	for (int i=(n-1-1)/2;i>=0;i--)
//	{
//		AdjustDown(a, n, i);
//	}
	int end = n - 1;
	while (end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}
